The present invention relates to information processing system organizations, more particularly to the parallel execution of computer programs or jobs, and even more particularly to techniques for enabling the speculative execution of concurrent jobs in an information processing system.
The traditional electronic computer has a single processing unit, and operates in accordance with a model whereby program instructions are retrieved (xe2x80x9cfetchedxe2x80x9d) one-by-one from an addressable memory, and then executed. Instructions that are to be executed in sequence are typically stored at sequential address locations within the memory. Exceptions to this sequential storage of instructions often occur, as for example when execution of a program segment is made conditional on some condition to be tested (e.g., whether two values are equal to one another), or when execution of the present program segment is to be interrupted by execution of another program segment (e.g., in response to a subroutine call or an interrupt). In such cases, program execution may take what is called a xe2x80x9cbranchxe2x80x9d or xe2x80x9cjumpxe2x80x9d to another location, whereby the fetching of instructions continues not with the next sequentially stored instruction, but with one stored at some other location within the memory.
Regardless of how the instructions are stored, it is the expectation of the programmer that the instructions that constitute a particular job will be executed in a particular order. A consequence of this expectation is that variables will be operated upon (e.g., modified or tested) in a particular sequence. Failure to comply with this expectation can result in a job that generates error-laden results.
It continues to be a goal of computer architects to design systems that can complete more work in less time. One approach for doing this has concentrated on making processing elements that are capable of operating faster. This approach has no impact on the programmer""s expectation of sequential program execution.
Another approach to improving processing speed has been to devise processors that are capable of operating concurrently. For example, in a so-called xe2x80x9csuper-scalarxe2x80x9d processor, the elements within a single processor are organized in such a way so as to permit several instructions to be performed concurrently. Another way to provide concurrent execution of instructions (so called xe2x80x9cinstruction level parallelxe2x80x9d (ILP) processing) is to provide multiple processing units, each attached to a shared memory, and to allocate individual instructions of a single program to be run on different ones of the processing units.
In order to ensure that the programmer""s expectation of sequential program execution is carried out, these architectures need to deal with two types of dependencies: xe2x80x9ccontrol dependencyxe2x80x9d and xe2x80x9cdata dependencyxe2x80x9d. Control dependency refers to the dependency of instructions to be executed only as a function of whether a conditional branch or jump has been taken in a preceding instruction. Data dependency is a dependency of instructions that use data that is created or changed by earlier instructions. The later-specified instructions may correctly execute only if the earlier instructions using the same data do not change the common data or have completed the change of the common data.
Rather than holding up the execution of an instruction whose execution is in some way dependent on the results generated by another instruction, these architectures often turn to the speculative execution of an instruction. That is, an instruction is executed as if there were no control or data dependency. The results of such a speculatively executed instructions must be undone in the event that it is later discovered that the originally planned sequential execution of the instructions would have achieved different results. U.S. Pat. No. 5,781,752 describes an ILP architecture that employs a table based data speculation circuit.
In yet another approach to increasing overall processing speed, some computer systems achieve high processing performance through a computer architecture known as Symmetric Multi Processing (SMP). In contrast to the fine-grained parallelism achieved by the above-described ILP architectures, the SMP architecture exploits coarse-grained parallelism that is either explicitly specified in programs designed in accordance with concurrent programming principles, or extracted from programs designed for sequential execution on a single-processor system during compilation.
Coarse-grained parallelism means task-level parallelism as opposed to instruction-level parallelism (although the two types of parallelism are not mutually exclusivexe2x80x94different tasks could be assigned to separate processors which each then employ instruction-level parallelism to carry out their respective task). In an SMP architecture, each one of several rather self-contained and complex computing tasks is carried out on a respective one of several processors. These tasks are mutually concurrent processes, threads or other similar constructs well-known in the information processing arts.
In another computer architecture having multiple processors, further parallelism is extracted during program execution by creating different threads from a single program, and assigning several tasks to different processors for concurrent execution. Because they derive from the same program, these threads may have dependencies similar to those described above with respect to instruction level parallelism. In particular, it is important that the two or more threads maintain data consistencyxe2x80x94that is, that a thread intended for later execution not use a data variable that has yet to be updated by a thread intended for earlier execution, and that the thread intended for later execution not modify a data variable that will subsequently be accessed by a thread intended for earlier execution. The occurrence of either of these events is called a xe2x80x9ccollisionxe2x80x9d.
Because of the possibility of collisions, it is common to insert locks (semaphores) into the code in order to maintain data consistency. This prevents any collisions from happening. However, algorithms that extract parallelism and insert locks for this purpose must be pessimistic because they must guarantee that a collision never occurs. This has the drawback of limiting the amount of parallelism that can be extracted.
As another solution to the problem presented when threads that share a data memory space are concurrently executed, one may employ speculative execution. In speculative execution, a collision between threads is detected and the erroneous results of executed threads are undone or purged.
In one architecture, one of a number of parallel threads is designated as a xe2x80x9ccommitted threadxe2x80x9d. All other concurrently executed threads are referred to as xe2x80x9cspeculative threadsxe2x80x9d. The committed thread is a thread that would be executed earliest if execution were sequential. The committed thread stores its state directly in a main memory. (As used herein, the term xe2x80x9cstatexe2x80x9d refers to the execution results of a thread or job, such as memory updates, heap, stack, signaling and so forth.) Speculative threads however temporarily store their states not in the shared memory, but in a memory (or memory area) distinct from the shared memory.
Since the committed thread is the thread intended for the earliest execution if execution were sequential, and since the results of the execution of the speculative threads do not affect the shared memory, there is no question concerning accuracy of the result of the committed thread. When execution of the committed thread is complete, it is simply retired. No particular action is taken with regard to the memory because an accurate state of the committed thread is already part of the shared memory.
After retirement of the committed thread, another thread is designated as a new committed thread. Designating a thread as a new committed thread is called xe2x80x9ccommitting a threadxe2x80x9d. The order in which threads are committed is always maintained the same as the order in which threads would be executed if they were executed sequentially. Committing a thread is done provided no collision is detected for the thread. When committing a thread that is speculatively executing (or has been speculatively executed), the temporarily stored memory states are copied to the shared memory.
If a speculative thread encounters a collision, the collision is resolved by purging the temporarily stored states of at least all later speculatively executed threads, and executing them anew. Purging the temporarily stored states is also referred to as a xe2x80x9croll-backxe2x80x9d or xe2x80x9cflushxe2x80x9d.
Speculative execution in conjunction with detecting collisions, and rolling back state changes when necessary offers a high potential for extracting parallelism from a program. Good performance is achieved so long as collisions do not occur too often (i.e., so long as the overhead associated with performing roll-backs is not excessive).
The xe2x80x9cProgram Language for EXchangesxe2x80x9d (PLEX) programming-model by Telefonaktiebolaget LM Ericsson employs essentially non-preemptive scheduling. Each PLEX program is divided into multiple jobs. A job is the execution of a sequential program that is initiated by a scheduler in response to an event, and that uninterruptedly continues until it finishes without external intervention. An event may result from an externally generated request (such as by a telephony subscriber) or it may result from a request generated by another job. Several jobs are generally queued in the scheduler, and carried out in a first-come-first-served manner.
PLEX lends itself well to parallel processing. Jobs are simply scheduled on multiple processors by a scheduler. However, when PLEX programs that are designed for execution on a single processor are executed on multiple processors in parallel, dependencies may emerge because jobs operate on a shared memory.
According to another concept developed at Telefonaktiebolaget LM Ericsson, called xe2x80x9cJob Parallel Computerxe2x80x9d (JPC), dependencies between jobs executed in parallel are resolved through speculative execution. In JPC, one and only one job at a time is committed. States of the committed job are effectuated immediately in the shared memory during execution. If there is no dependency when execution of the committed job finishes, a speculatively executed job becomes committed as determined by the scheduler. States generated by the speculatively executed job being committed take effect in the shared memory only after the previously committed job finishes execution and the speculatively executed job becomes the new committed job.
In the event of a dependency, speculatively executed jobs are flushed and execution of the speculatively executed jobs is repeated. A strict scheduling order is always maintained.
Dedicated hardware is used for managing coarse-grained parallelism with speculative execution. The dedicated hardware includes a memory area for temporarily storing information from speculative execution of threads or jobs. When it is time to commit a speculatively executed job, the information is copied from the temporary storage area into the shared memory.
The existing approaches to enabling coarse-level concurrent execution of jobs have a number of problems. First, they generally require dedicated hardware support for managing coarse grained parallelism with speculative execution. However, it would be desirable to be able to benefit from the full potential of computer architectures implemented with standard processors. In particular, programs designed under the sequential programming paradigm have not benefitted from the coarse-grained parallel capabilities of a multi-processor based computer that uses standard processors.
Furthermore, the need to copy the speculatively executed job""s data from the temporary storage area into the shared memory at the time of commitment adds an additional overhead that slows down the overall information processing rate.
It is therefore an object of the present invention to provide a technique for enabling coarse-grained execution of concurrent jobs that does not require special support hardware to handle speculative execution of jobs.
In accordance with one aspect of the present invention, the foregoing and other objects are achieved in a computer system that includes a paged physical memory. In some embodiments that employ a xe2x80x9cprivatizationxe2x80x9d strategy to maintaining speculative execution states in a reversible manner, a set of shared virtual pages are defined that stores data that are shared by a first job and a second job. A set of shared physical pages is also defined in the paged physical memory, wherein there is a one-to-one correspondence between the set of shared virtual pages and the set of shared physical pages. A first memory map causes the first job to access a first shared physical page in the memory whenever the first job accesses any location in a first virtual page in the set of shared virtual pages, wherein the first shared physical page is in the set of shared physical pages. A second memory map also causes the second job to access the first shared physical page in the shared memory whenever the second job accesses any location in the first virtual page. However, the second memory map also causes the second job to access a private physical page whenever the second job accesses any location in a second virtual page in the set of shared virtual pages, wherein the private physical page is not in the set of shared physical pages. In this manner, speculative data will be maintained in the private physical page, separate and apart from the shared physical page.
In another aspect, the private physical page may be created in response to a sequentially first write operation directed to the second virtual page by the second job. That is, the private physical page may be created on demand.
In still another aspect, creation of the private physical page may be performed in response to a first write protect interrupt associated with the sequentially first write operation directed to the second virtual page by the second job.
In yet another aspect, a translation lookaside buffer associated with the second job is initialized with one or more entries from the first memory map. Write protection is initially enabled in connection with one or more pages identified by the one or more entries from the first memory map.
In still another aspect, write protect associated with the second virtual page is disabled after the first write protect interrupt. This will prevent further write protect interrupts associated with the second job accessing the second virtual page.
In another aspect, a collision between the first job and the second job will cause the private physical page to be released. Thus, it takes very little effort to xe2x80x9crestorexe2x80x9d the state of the shared memory to its original condition because it has never been changed.
In still another aspect, if both the first job and the second job complete without an occurrence of a collision between the two, the set of shared physical pages is redefined to include the private physical page in place of the second shared physical page. This has the further advantage of avoiding the need to copy the speculatively generated data into a shared memory space.
In yet another aspect, the second memory map comprises a shared page table and a private page table. The shared page table stores mappings between shared virtual pages and shared physical pages, whereas the private page table stores mappings only between shared virtual pages and private physical pages. A two-level table is thereby created.
In still another aspect, using the second memory map to cause the second job to access the first shared physical page in the shared memory whenever the second job accesses any location in the first virtual page comprises first determining whether a mapping associated with the first virtual page is stored in the private page table; and then locating a mapping associated with the first virtual page in the shared page table if the private page table does not have stored therein any mapping associated with the first virtual page.
In alternative embodiments, a xe2x80x9cnon-privatizationxe2x80x9d strategy is adopted to maintain speculative data. Again, a set of shared virtual pages is defined that stores data that are shared by a first job and a second job; and a set of shared physical pages is defined in the paged physical memory, wherein there is a one-to-one correspondence between the set of shared virtual pages and the set of shared physical pages. A first memory map causes the first job to access a first shared physical page in the memory whenever the first job accesses any location in a first virtual page in the set of shared virtual pages, wherein the first shared physical page is in the set of shared physical pages. A second memory map causes the second job to access the first shared physical page in the shared memory whenever the second job accesses any location in the first virtual page. In these embodiments, a backup physical page is created in response to a sequentially first write operation directed to the first virtual page by the second job, wherein the backup physical page includes a copy of all data contained in the first shared physical page, and wherein the backup physical page is not in the set of shared physical pages. Both the first and second jobs will continue to access the same shared physical page. However, the backup physical page can serve to maintain the original state of the shared physical page, should restoration become necessary due to a collision between jobs.
In another aspect of these embodiments, in the event of a collision, the set of shared physical pages is redefined to include the backup physical page in place of the first shared physical page. This advantageously eliminates the need to actually copy data from the backup physical page to the original shared physical page.
If both the first job and the second jobs complete without an occurrence of a collision between the two, the backup physical page may be released.